package main

import (
	"fmt"
)

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func insert(intervals [][]int, newInterval []int) [][]int {
	result := make([][]int, 0, len(intervals)+1)
	merged := false
	left, right := newInterval[0], newInterval[1]
	for _, interval := range intervals {
		if interval[1] < left {
			result = append(result, interval)
		} else if interval[0] > right {
			if !merged {
				merged = true
				result = append(result, []int{left, right})
			}
			result = append(result, interval)
		} else {
			left = min(left, interval[0])
			right = max(right, interval[1])
		}
	}
	if !merged {
		result = append(result, []int{left, right})
	}
	return result
}

func main() {
	//fmt.Printf("%#v\n", insert([][]int{}, []int{5, 7}))
	//fmt.Printf("%#v\n", insert([][]int{{1, 2}}, []int{5, 7}))
	fmt.Printf("%#v\n", insert([][]int{{1, 3}, {6, 9}}, []int{2, 5}))
}
